The present disclosure relates generally to random number generation, and more particularly to methods for improving the entropy quality of a random number generator by injecting central processing unit (CPU) time jitter.
Secure cryptography is dependent on the ability to generate unpredictable random numbers. Thus, all cryptographic modules (hardware or software based) must have access to a high-quality random number generator (RNG), sometimes called a random bit generator (RBG). There are two classes of RNG: (1) a true random number generator (TRNG), sometimes called a non-deterministic random number generator (NDRNG); and (2) a pseudo-random number generator (PRNG), sometimes called the deterministic random number generator (DRNG). A true random number generator (TRNG) is a genuine random number generator. It extracts entropy from one or more noise sources and compresses it into a stream of random bytes. For hardware-based cryptographic modules, the TRNG noise sources are hardware features built into the device, such as sampling thermal noise from a resistor. Software based cryptographic module TRNGs tend to have fewer available noise sources. A pseudo-random number generator (PRNG) takes a seed as input and produces a stream of output that looks random, but is actually not random at all (hence the name ‘deterministic’). In a well-designed PRNG, the output is indistinguishable from random provided the seed is random and kept secret. PRNGs also have a much higher throughput than TRNGs. Thus, a PRNG is usually seeded from a separate TRNG, then used as the RNG for the module.
Conventionally, random number generators use real clock time or CPU time as a randomness factor to generate random numbers. Conventional random number generators use a loop to get a time value, calculate a time difference, update the time value, select a lower order bit of the time delta as a candidate bit, and perform a von Neumann analysis to generate a random bit. Note that if the loop always executed at a constant rate, the algorithm would loop forever, since the candidate bit would always be the same. Naturally occurring jitter is a phenomenon of all computing systems. Hardware and operating systems are constantly servicing events that happen beneath the visibility of a virtual program. Page faults, I/O completion interrupts, level 1 (L1) cache misses, etc. are examples of such events, all of which add jitter to any executing program loop. If you consider a software based TRNG running as a virtual program, naturally occurring jitter is beyond the TRNG's control and, thus, unpredictable. With the continued drop in computing hardware prices, today's computing systems are more highly tuned than in the past. The availability of more RAM and larger L1 caches results in less interruptions. Hence, naturally occurring jitter is becoming scare. It is desirable to add a new randomness factor into the random number generator.
Therefore, heretofore unaddressed needs still exist in the art to address the aforementioned deficiencies and inadequacies.